#include<iostream>
#include<queue>
#include<stack>
using namespace std;
#define INT_MAX
#define maxvexnums 10
//bfs_最短路径
int d[maxvexnums];
int path[maxvexnums];
//拓扑排序
stack<int> S;//存储入度为0的顶点
int print[maxvexnums]={-1};
//bfs
queue<int> Q;
bool visited[maxvexnums];
//dijkstra

typedef struct ArcNode{
    int adjvex;
    int weight;
    struct ArcNode *next;
}ArcNode;
typedef struct VNode{
    char data;
    int indegree;
    ArcNode *firstedge;
}VNode,adjList[maxvexnums];
typedef struct MGraph{
    adjList vertices;
    int vexnums,arcnums;
}MGraph;
void create_mg(MGraph *mg){
    int i,j,k,weight;
    printf("请输入顶点数和边数:");
    scanf("%d%d", &mg->vexnums,&mg->arcnums);
    printf("请输入顶点信息:");
    for(i=0;i<mg->vexnums;i++){
        getchar();
        scanf("%c",&mg->vertices[i].data);
        mg->vertices[i].indegree=0;
        mg->vertices[i].firstedge=NULL;
    }
    printf("输入vi,vj所对应的i,j,weight:");
    for(k=0;k<mg->arcnums;k++){
        scanf("%d%d%d",&i,&j,&weight);
        ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode)*1);
        p->adjvex=j;
        p->weight=weight;
        mg->vertices[p->adjvex].indegree++;
        p->next=mg->vertices[i].firstedge;
        mg->vertices[i].firstedge=p;//头插法

        //无向图
        // ArcNode *q=(ArcNode *)malloc(sizeof(ArcNode)*1);
        // q->adjvex=i;
        // q->next=mg->vertices[j].firstedge;
        // mg->vertices[j].firstedge=q;
    }
}
int FirstNeighbor(MGraph mg,int v){
    if(mg.vertices[v].firstedge)
        return mg.vertices[v].firstedge->adjvex;
    else   
        return -1;
}
int NextNeighbor(MGraph mg,int v,int w){
    ArcNode *p=mg.vertices[v].firstedge;
    while(p->adjvex!=w)
            p=p->next;
    if(p->next)
        return p->next->adjvex;
    else 
        return -1;

}
void visit(MGraph mg,int v){
    printf("(%d)%c->",mg.vertices[v].indegree,mg.vertices[v].data);
}
void bfs(MGraph mg,int v){
    visit(mg,v);
    visited[v]=true;
    Q.push(v);
    while(!Q.empty()){
        v=Q.front();
        Q.pop();
        for(int w=FirstNeighbor(mg,v);w>=0;w=NextNeighbor(mg,v,w)){
            if(!visited[w]){
                visit(mg,w);
                visited[w]=true;
                Q.push(w);
            }
        }
    }
}
void bfs_traverse(MGraph mg){
    for(int i=0;i<mg.vexnums;i++){
        visited[i]=false;
    }
    for(int i=0;i<mg.vexnums;i++){
        if(!visited[i])
            bfs(mg,i);
    }
}
void mindistance_bfs(MGraph mg,int u){
    for(int i=0;i<mg.vexnums;i++){
        d[i]=INT_MAX;//初始化长度无穷大
        path[i]=-1;
    }
    d[u]=0;
    visited[u]=true;
    Q.push(u);
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        for(int w=FirstNeighbor(mg,u);w>=0;w=NextNeighbor(mg,u,w)){
            if(!visited[w]){//w为u未访问节点
                d[w]=d[u]+1;//路径长度+1
                path[w]=u;//u0->w最短路径上的直接前驱
                visited[w]=true;
                Q.push(w);
            }
        }
    }
}
void minstance_dijkstra(MGraph mg,int u){
    
}

bool TopologicalSort(MGraph mg){
    int v;
    ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode)*1);
    for(int i=0;i<mg.vexnums;i++){
        if(mg.vertices[i].indegree==0)
            S.push(i);//所有入度为0的顶点入栈
        int count=0;//记录当前已经输出节点数
        while(!S.empty()){
            i=S.top();
            S.pop();
            print[count++]=i;//输出顶点
            for(p=mg.vertices[i].firstedge;p;p=p->next){
                //将所有i指向的顶点入度减1，且将入度减为0的顶点压入栈
                v=p->adjvex;
                if(!(--mg.vertices[v].indegree))
                    S.push(v);
            }
        }
        if(count<mg.vexnums)
            return false;//排序失败，图中有回路
        else    
            return true;
    }
}
int main(){
    MGraph mg;
    create_mg(&mg);
    bfs_traverse(mg);
    mindistance_bfs(mg,0);
    printf("\n%d",TopologicalSort(mg));
    minstance_dijkstra(mg,0);
    return 0;
}